package com.lw.leetcode.hash.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * LCP 46. 志愿者调配
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/10 13:35
 */
public class VolunteerDeployment {

    public int[] volunteerDeployment(int[] finalCnt, long totalNum, int[][] edges, int[][] plans) {
        int length = finalCnt.length + 1;
        long[] counta = new long[length];
        long[] countb = new long[length];

        for (int i = 1; i < length; i++) {
            countb[i] = finalCnt[i - 1];
        }
        counta[0] = 1;

        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] edge : edges) {
            map.computeIfAbsent(edge[0], v-> new ArrayList<>()).add(edge[1]);
            map.computeIfAbsent(edge[1], v-> new ArrayList<>()).add(edge[0]);
        }

        for (int i = plans.length - 1; i >= 0; i--) {
            int[] plan = plans[i];
            int p = plan[0];
            int index = plan[1];
            if (p == 1) {
                counta[index] <<= 1;
                countb[index] <<= 1;
            } else if (p == 2) {
                List<Integer> list = map.get(index);
                if(list == null) {
                    continue;
                }
                long a = counta[index];
                long b = countb[index];
                for (int in : list) {
                    counta[in] -= a;
                    countb[in] -= b;
                }
            } else {
                List<Integer> list = map.get(index);
                if(list == null) {
                    continue;
                }
                long a = counta[index];
                long b = countb[index];
                for (int in : list) {
                    counta[in] += a;
                    countb[in] += b;
                }
            }
        }
        long suma = 0;
        long sumb = 0;
        for (long l : counta) {
            suma += l;
        }
        for (long l : countb) {
            sumb += l;
        }
        long v = (totalNum - sumb) / suma;
        int[] arr = new int[length];

        for (int i = 0; i < length; i++) {
            arr[i] = (int) (counta[i] * v + countb[i]);
        }
        return arr;
    }

}
